home *** CD-ROM | disk | FTP | other *** search
/ PC/CD Gamer UK 120 / CD Gamer Issue 120 (March 2003) (Disc 2).ISO / mods / Q2_Codered / codeRED1_0.exe / Data1.cab / sv_world.c < prev    next >
Encoding:
C/C++ Source or Header  |  2002-08-13  |  14.6 KB  |  660 lines
  1. /*
  2. Copyright (C) 1997-2001 Id Software, Inc.
  3.  
  4. This program is free software; you can redistribute it and/or
  5. modify it under the terms of the GNU General Public License
  6. as published by the Free Software Foundation; either version 2
  7. of the License, or (at your option) any later version.
  8.  
  9. This program is distributed in the hope that it will be useful,
  10. but WITHOUT ANY WARRANTY; without even the implied warranty of
  11. MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  
  12.  
  13. See the GNU General Public License for more details.
  14.  
  15. You should have received a copy of the GNU General Public License
  16. along with this program; if not, write to the Free Software
  17. Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.
  18.  
  19. */
  20. // world.c -- world query functions
  21.  
  22. #include "server.h"
  23.  
  24. /*
  25. ===============================================================================
  26.  
  27. ENTITY AREA CHECKING
  28.  
  29. FIXME: this use of "area" is different from the bsp file use
  30. ===============================================================================
  31. */
  32.  
  33. // (type *)STRUCT_FROM_LINK(link_t *link, type, member)
  34. // ent = STRUCT_FROM_LINK(link,entity_t,order)
  35. // FIXME: remove this mess!
  36. #define    STRUCT_FROM_LINK(l,t,m) ((t *)((byte *)l - (int)&(((t *)0)->m)))
  37.  
  38. #define    EDICT_FROM_AREA(l) STRUCT_FROM_LINK(l,edict_t,area)
  39.  
  40. typedef struct areanode_s
  41. {
  42.     int        axis;        // -1 = leaf node
  43.     float    dist;
  44.     struct areanode_s    *children[2];
  45.     link_t    trigger_edicts;
  46.     link_t    solid_edicts;
  47. } areanode_t;
  48.  
  49. #define    AREA_DEPTH    4
  50. #define    AREA_NODES    32
  51.  
  52. areanode_t    sv_areanodes[AREA_NODES];
  53. int            sv_numareanodes;
  54.  
  55. float    *area_mins, *area_maxs;
  56. edict_t    **area_list;
  57. int        area_count, area_maxcount;
  58. int        area_type;
  59.  
  60. int SV_HullForEntity (edict_t *ent);
  61.  
  62.  
  63. // ClearLink is used for new headnodes
  64. void ClearLink (link_t *l)
  65. {
  66.     l->prev = l->next = l;
  67. }
  68.  
  69. void RemoveLink (link_t *l)
  70. {
  71.     l->next->prev = l->prev;
  72.     l->prev->next = l->next;
  73. }
  74.  
  75. void InsertLinkBefore (link_t *l, link_t *before)
  76. {
  77.     l->next = before;
  78.     l->prev = before->prev;
  79.     l->prev->next = l;
  80.     l->next->prev = l;
  81. }
  82.  
  83. /*
  84. ===============
  85. SV_CreateAreaNode
  86.  
  87. Builds a uniformly subdivided tree for the given world size
  88. ===============
  89. */
  90. areanode_t *SV_CreateAreaNode (int depth, vec3_t mins, vec3_t maxs)
  91. {
  92.     areanode_t    *anode;
  93.     vec3_t        size;
  94.     vec3_t        mins1, maxs1, mins2, maxs2;
  95.  
  96.     anode = &sv_areanodes[sv_numareanodes];
  97.     sv_numareanodes++;
  98.  
  99.     ClearLink (&anode->trigger_edicts);
  100.     ClearLink (&anode->solid_edicts);
  101.     
  102.     if (depth == AREA_DEPTH)
  103.     {
  104.         anode->axis = -1;
  105.         anode->children[0] = anode->children[1] = NULL;
  106.         return anode;
  107.     }
  108.     
  109.     VectorSubtract (maxs, mins, size);
  110.     if (size[0] > size[1])
  111.         anode->axis = 0;
  112.     else
  113.         anode->axis = 1;
  114.     
  115.     anode->dist = 0.5 * (maxs[anode->axis] + mins[anode->axis]);
  116.     VectorCopy (mins, mins1);    
  117.     VectorCopy (mins, mins2);    
  118.     VectorCopy (maxs, maxs1);    
  119.     VectorCopy (maxs, maxs2);    
  120.     
  121.     maxs1[anode->axis] = mins2[anode->axis] = anode->dist;
  122.     
  123.     anode->children[0] = SV_CreateAreaNode (depth+1, mins2, maxs2);
  124.     anode->children[1] = SV_CreateAreaNode (depth+1, mins1, maxs1);
  125.  
  126.     return anode;
  127. }
  128.  
  129. /*
  130. ===============
  131. SV_ClearWorld
  132.  
  133. ===============
  134. */
  135. void SV_ClearWorld (void)
  136. {
  137.     memset (sv_areanodes, 0, sizeof(sv_areanodes));
  138.     sv_numareanodes = 0;
  139.     SV_CreateAreaNode (0, sv.models[1]->mins, sv.models[1]->maxs);
  140. }
  141.  
  142.  
  143. /*
  144. ===============
  145. SV_UnlinkEdict
  146.  
  147. ===============
  148. */
  149. void SV_UnlinkEdict (edict_t *ent)
  150. {
  151.     if (!ent->area.prev)
  152.         return;        // not linked in anywhere
  153.     RemoveLink (&ent->area);
  154.     ent->area.prev = ent->area.next = NULL;
  155. }
  156.  
  157.  
  158. /*
  159. ===============
  160. SV_LinkEdict
  161.  
  162. ===============
  163. */
  164. #define MAX_TOTAL_ENT_LEAFS        128
  165. void SV_LinkEdict (edict_t *ent)
  166. {
  167.     areanode_t    *node;
  168.     int            leafs[MAX_TOTAL_ENT_LEAFS];
  169.     int            clusters[MAX_TOTAL_ENT_LEAFS];
  170.     int            num_leafs;
  171.     int            i, j, k;
  172.     int            area;
  173.     int            topnode;
  174.  
  175.     if (ent->area.prev)
  176.         SV_UnlinkEdict (ent);    // unlink from old position
  177.         
  178.     if (ent == ge->edicts)
  179.         return;        // don't add the world
  180.  
  181.     if (!ent->inuse)
  182.         return;
  183.  
  184.     // set the size
  185.     VectorSubtract (ent->maxs, ent->mins, ent->size);
  186.     
  187.     // encode the size into the entity_state for client prediction
  188.     if (ent->solid == SOLID_BBOX && !(ent->svflags & SVF_DEADMONSTER))
  189.     {    // assume that x/y are equal and symetric
  190.         i = ent->maxs[0]/8;
  191.         if (i<1)
  192.             i = 1;
  193.         if (i>31)
  194.             i = 31;
  195.  
  196.         // z is not symetric
  197.         j = (-ent->mins[2])/8;
  198.         if (j<1)
  199.             j = 1;
  200.         if (j>31)
  201.             j = 31;
  202.  
  203.         // and z maxs can be negative...
  204.         k = (ent->maxs[2]+32)/8;
  205.         if (k<1)
  206.             k = 1;
  207.         if (k>63)
  208.             k = 63;
  209.  
  210.         ent->s.solid = (k<<10) | (j<<5) | i;
  211.     }
  212.     else if (ent->solid == SOLID_BSP)
  213.     {
  214.         ent->s.solid = 31;        // a solid_bbox will never create this value
  215.     }
  216.     else
  217.         ent->s.solid = 0;
  218.  
  219.     // set the abs box
  220.     if (ent->solid == SOLID_BSP && 
  221.     (ent->s.angles[0] || ent->s.angles[1] || ent->s.angles[2]) )
  222.     {    // expand for rotation
  223.         float        max, v;
  224.         int            i;
  225.  
  226.         max = 0;
  227.         for (i=0 ; i<3 ; i++)
  228.         {
  229.             v =fabs( ent->mins[i]);
  230.             if (v > max)
  231.                 max = v;
  232.             v =fabs( ent->maxs[i]);
  233.             if (v > max)
  234.                 max = v;
  235.         }
  236.         for (i=0 ; i<3 ; i++)
  237.         {
  238.             ent->absmin[i] = ent->s.origin[i] - max;
  239.             ent->absmax[i] = ent->s.origin[i] + max;
  240.         }
  241.     }
  242.     else
  243.     {    // normal
  244.         VectorAdd (ent->s.origin, ent->mins, ent->absmin);    
  245.         VectorAdd (ent->s.origin, ent->maxs, ent->absmax);
  246.     }
  247.  
  248.     // because movement is clipped an epsilon away from an actual edge,
  249.     // we must fully check even when bounding boxes don't quite touch
  250.     ent->absmin[0] -= 1;
  251.     ent->absmin[1] -= 1;
  252.     ent->absmin[2] -= 1;
  253.     ent->absmax[0] += 1;
  254.     ent->absmax[1] += 1;
  255.     ent->absmax[2] += 1;
  256.  
  257. // link to PVS leafs
  258.     ent->num_clusters = 0;
  259.     ent->areanum = 0;
  260.     ent->areanum2 = 0;
  261.  
  262.     //get all leafs, including solids
  263.     num_leafs = CM_BoxLeafnums (ent->absmin, ent->absmax,
  264.         leafs, MAX_TOTAL_ENT_LEAFS, &topnode);
  265.  
  266.     // set areas
  267.     for (i=0 ; i<num_leafs ; i++)
  268.     {
  269.         clusters[i] = CM_LeafCluster (leafs[i]);
  270.         area = CM_LeafArea (leafs[i]);
  271.         if (area)
  272.         {    // doors may legally straggle two areas,
  273.             // but nothing should evern need more than that
  274.             if (ent->areanum && ent->areanum != area)
  275.             {
  276.                 if (ent->areanum2 && ent->areanum2 != area && sv.state == ss_loading)
  277.                     Com_DPrintf ("Object touching 3 areas at %f %f %f\n",
  278.                     ent->absmin[0], ent->absmin[1], ent->absmin[2]);
  279.                 ent->areanum2 = area;
  280.             }
  281.             else
  282.                 ent->areanum = area;
  283.         }
  284.     }
  285.  
  286.     if (num_leafs >= MAX_TOTAL_ENT_LEAFS)
  287.     {    // assume we missed some leafs, and mark by headnode
  288.         ent->num_clusters = -1;
  289.         ent->headnode = topnode;
  290.     }
  291.     else
  292.     {
  293.         ent->num_clusters = 0;
  294.         for (i=0 ; i<num_leafs ; i++)
  295.         {
  296.             if (clusters[i] == -1)
  297.                 continue;        // not a visible leaf
  298.             for (j=0 ; j<i ; j++)
  299.                 if (clusters[j] == clusters[i])
  300.                     break;
  301.             if (j == i)
  302.             {
  303.                 if (ent->num_clusters == MAX_ENT_CLUSTERS)
  304.                 {    // assume we missed some leafs, and mark by headnode
  305.                     ent->num_clusters = -1;
  306.                     ent->headnode = topnode;
  307.                     break;
  308.                 }
  309.  
  310.                 ent->clusternums[ent->num_clusters++] = clusters[i];
  311.             }
  312.         }
  313.     }
  314.  
  315.     // if first time, make sure old_origin is valid
  316.     if (!ent->linkcount)
  317.     {
  318.         VectorCopy (ent->s.origin, ent->s.old_origin);
  319.     }
  320.     ent->linkcount++;
  321.  
  322.     if (ent->solid == SOLID_NOT)
  323.         return;
  324.  
  325. // find the first node that the ent's box crosses
  326.     node = sv_areanodes;
  327.     while (1)
  328.     {
  329.         if (node->axis == -1)
  330.             break;
  331.         if (ent->absmin[node->axis] > node->dist)
  332.             node = node->children[0];
  333.         else if (ent->absmax[node->axis] < node->dist)
  334.             node = node->children[1];
  335.         else
  336.             break;        // crosses the node
  337.     }
  338.     
  339.     // link it in    
  340.     if (ent->solid == SOLID_TRIGGER)
  341.         InsertLinkBefore (&ent->area, &node->trigger_edicts);
  342.     else
  343.         InsertLinkBefore (&ent->area, &node->solid_edicts);
  344.  
  345. }
  346.  
  347.  
  348. /*
  349. ====================
  350. SV_AreaEdicts_r
  351.  
  352. ====================
  353. */
  354. void SV_AreaEdicts_r (areanode_t *node)
  355. {
  356.     link_t        *l, *next, *start;
  357.     edict_t        *check;
  358.     int            count;
  359.  
  360.     count = 0;
  361.  
  362.     // touch linked edicts
  363.     if (area_type == AREA_SOLID)
  364.         start = &node->solid_edicts;
  365.     else
  366.         start = &node->trigger_edicts;
  367.  
  368.     for (l=start->next  ; l != start ; l = next)
  369.     {
  370.         next = l->next;
  371.         check = EDICT_FROM_AREA(l);
  372.  
  373.         if (check->solid == SOLID_NOT)
  374.             continue;        // deactivated
  375.         if (check->absmin[0] > area_maxs[0]
  376.         || check->absmin[1] > area_maxs[1]
  377.         || check->absmin[2] > area_maxs[2]
  378.         || check->absmax[0] < area_mins[0]
  379.         || check->absmax[1] < area_mins[1]
  380.         || check->absmax[2] < area_mins[2])
  381.             continue;        // not touching
  382.  
  383.         if (area_count == area_maxcount)
  384.         {
  385.             Com_Printf ("SV_AreaEdicts: MAXCOUNT\n");
  386.             return;
  387.         }
  388.  
  389.         area_list[area_count] = check;
  390.         area_count++;
  391.     }
  392.     
  393.     if (node->axis == -1)
  394.         return;        // terminal node
  395.  
  396.     // recurse down both sides
  397.     if ( area_maxs[node->axis] > node->dist )
  398.         SV_AreaEdicts_r ( node->children[0] );
  399.     if ( area_mins[node->axis] < node->dist )
  400.         SV_AreaEdicts_r ( node->children[1] );
  401. }
  402.  
  403. /*
  404. ================
  405. SV_AreaEdicts
  406. ================
  407. */
  408. int SV_AreaEdicts (vec3_t mins, vec3_t maxs, edict_t **list,
  409.     int maxcount, int areatype)
  410. {
  411.     area_mins = mins;
  412.     area_maxs = maxs;
  413.     area_list = list;
  414.     area_count = 0;
  415.     area_maxcount = maxcount;
  416.     area_type = areatype;
  417.  
  418.     SV_AreaEdicts_r (sv_areanodes);
  419.  
  420.     return area_count;
  421. }
  422.  
  423.  
  424. //===========================================================================
  425.  
  426. /*
  427. =============
  428. SV_PointContents
  429. =============
  430. */
  431. int SV_PointContents (vec3_t p)
  432. {
  433.     edict_t        *touch[MAX_EDICTS], *hit;
  434.     int            i, num;
  435.     int            contents, c2;
  436.     int            headnode;
  437.     float        *angles;
  438.  
  439.     // get base contents from world
  440.     contents = CM_PointContents (p, sv.models[1]->headnode);
  441.  
  442.     // or in contents from all the other entities
  443.     num = SV_AreaEdicts (p, p, touch, MAX_EDICTS, AREA_SOLID);
  444.  
  445.     for (i=0 ; i<num ; i++)
  446.     {
  447.         hit = touch[i];
  448.  
  449.         // might intersect, so do an exact clip
  450.         headnode = SV_HullForEntity (hit);
  451.         angles = hit->s.angles;
  452.         if (hit->solid != SOLID_BSP)
  453.             angles = vec3_origin;    // boxes don't rotate
  454.  
  455.         c2 = CM_TransformedPointContents (p, headnode, hit->s.origin, hit->s.angles);
  456.  
  457.         contents |= c2;
  458.     }
  459.  
  460.     return contents;
  461. }
  462.  
  463.  
  464.  
  465. typedef struct
  466. {
  467.     vec3_t        boxmins, boxmaxs;// enclose the test object along entire move
  468.     float        *mins, *maxs;    // size of the moving object
  469.     vec3_t        mins2, maxs2;    // size when clipping against mosnters
  470.     float        *start, *end;
  471.     trace_t        trace;
  472.     edict_t        *passedict;
  473.     int            contentmask;
  474. } moveclip_t;
  475.  
  476.  
  477.  
  478. /*
  479. ================
  480. SV_HullForEntity
  481.  
  482. Returns a headnode that can be used for testing or clipping an
  483. object of mins/maxs size.
  484. Offset is filled in to contain the adjustment that must be added to the
  485. testing object's origin to get a point to use with the returned hull.
  486. ================
  487. */
  488. int SV_HullForEntity (edict_t *ent)
  489. {
  490.     cmodel_t    *model;
  491.  
  492. // decide which clipping hull to use, based on the size
  493.     if (ent->solid == SOLID_BSP)
  494.     {    // explicit hulls in the BSP model
  495.         model = sv.models[ ent->s.modelindex ];
  496.  
  497.         if (!model)
  498.             Com_Error (ERR_FATAL, "MOVETYPE_PUSH with a non bsp model");
  499.  
  500.         return model->headnode;
  501.     }
  502.  
  503.     // create a temp hull from bounding box sizes
  504.  
  505.     return CM_HeadnodeForBox (ent->mins, ent->maxs);
  506. }
  507.  
  508.  
  509. //===========================================================================
  510.  
  511. /*
  512. ====================
  513. SV_ClipMoveToEntities
  514.  
  515. ====================
  516. */
  517. void SV_ClipMoveToEntities ( moveclip_t *clip )
  518. {
  519.     int            i, num;
  520.     edict_t        *touchlist[MAX_EDICTS], *touch;
  521.     trace_t        trace;
  522.     int            headnode;
  523.     float        *angles;
  524.  
  525.     num = SV_AreaEdicts (clip->boxmins, clip->boxmaxs, touchlist
  526.         , MAX_EDICTS, AREA_SOLID);
  527.  
  528.     // be careful, it is possible to have an entity in this
  529.     // list removed before we get to it (killtriggered)
  530.     for (i=0 ; i<num ; i++)
  531.     {
  532.         touch = touchlist[i];
  533.         if (touch->solid == SOLID_NOT)
  534.             continue;
  535.         if (touch == clip->passedict)
  536.             continue;
  537.         if (clip->trace.allsolid)
  538.             return;
  539.         if (clip->passedict)
  540.         {
  541.              if (touch->owner == clip->passedict)
  542.                 continue;    // don't clip against own missiles
  543.             if (clip->passedict->owner == touch)
  544.                 continue;    // don't clip against owner
  545.         }
  546.  
  547.         if ( !(clip->contentmask & CONTENTS_DEADMONSTER)
  548.         && (touch->svflags & SVF_DEADMONSTER) )
  549.                 continue;
  550.  
  551.         // might intersect, so do an exact clip
  552.         headnode = SV_HullForEntity (touch);
  553.         angles = touch->s.angles;
  554.         if (touch->solid != SOLID_BSP)
  555.             angles = vec3_origin;    // boxes don't rotate
  556.  
  557.         if (touch->svflags & SVF_MONSTER)
  558.             trace = CM_TransformedBoxTrace (clip->start, clip->end,
  559.                 clip->mins2, clip->maxs2, headnode, clip->contentmask,
  560.                 touch->s.origin, angles);
  561.         else
  562.             trace = CM_TransformedBoxTrace (clip->start, clip->end,
  563.                 clip->mins, clip->maxs, headnode,  clip->contentmask,
  564.                 touch->s.origin, angles);
  565.  
  566.         if (trace.allsolid || trace.startsolid ||
  567.         trace.fraction < clip->trace.fraction)
  568.         {
  569.             trace.ent = touch;
  570.              if (clip->trace.startsolid)
  571.             {
  572.                 clip->trace = trace;
  573.                 clip->trace.startsolid = true;
  574.             }
  575.             else
  576.                 clip->trace = trace;
  577.         }
  578.         else if (trace.startsolid)
  579.             clip->trace.startsolid = true;
  580.     }
  581. }
  582.  
  583.  
  584. /*
  585. ==================
  586. SV_TraceBounds
  587. ==================
  588. */
  589. void SV_TraceBounds (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, vec3_t boxmins, vec3_t boxmaxs)
  590. {
  591. #if 0
  592. // debug to test against everything
  593. boxmins[0] = boxmins[1] = boxmins[2] = -9999;
  594. boxmaxs[0] = boxmaxs[1] = boxmaxs[2] = 9999;
  595. #else
  596.     int        i;
  597.     
  598.     for (i=0 ; i<3 ; i++)
  599.     {
  600.         if (end[i] > start[i])
  601.         {
  602.             boxmins[i] = start[i] + mins[i] - 1;
  603.             boxmaxs[i] = end[i] + maxs[i] + 1;
  604.         }
  605.         else
  606.         {
  607.             boxmins[i] = end[i] + mins[i] - 1;
  608.             boxmaxs[i] = start[i] + maxs[i] + 1;
  609.         }
  610.     }
  611. #endif
  612. }
  613.  
  614. /*
  615. ==================
  616. SV_Trace
  617.  
  618. Moves the given mins/maxs volume through the world from start to end.
  619.  
  620. Passedict and edicts owned by passedict are explicitly not checked.
  621.  
  622. ==================
  623. */
  624. trace_t SV_Trace (vec3_t start, vec3_t mins, vec3_t maxs, vec3_t end, edict_t *passedict, int contentmask)
  625. {
  626.     moveclip_t    clip;
  627.  
  628.     if (!mins)
  629.         mins = vec3_origin;
  630.     if (!maxs)
  631.         maxs = vec3_origin;
  632.  
  633.     memset ( &clip, 0, sizeof ( moveclip_t ) );
  634.  
  635.     // clip to world
  636.     clip.trace = CM_BoxTrace (start, end, mins, maxs, 0, contentmask);
  637.     clip.trace.ent = ge->edicts;
  638.     if (clip.trace.fraction == 0)
  639.         return clip.trace;        // blocked by the world
  640.  
  641.     clip.contentmask = contentmask;
  642.     clip.start = start;
  643.     clip.end = end;
  644.     clip.mins = mins;
  645.     clip.maxs = maxs;
  646.     clip.passedict = passedict;
  647.  
  648.     VectorCopy (mins, clip.mins2);
  649.     VectorCopy (maxs, clip.maxs2);
  650.     
  651.     // create the bounding box of the entire move
  652.     SV_TraceBounds ( start, clip.mins2, clip.maxs2, end, clip.boxmins, clip.boxmaxs );
  653.  
  654.     // clip to other solid entities
  655.     SV_ClipMoveToEntities ( &clip );
  656.  
  657.     return clip.trace;
  658. }
  659.  
  660.